

// 23.合并K个升序链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* phead = new ListNode , *tail = phead;
        // 使用优先级队列来解决
        auto comp = [](ListNode* x , ListNode* y)
        {
            return x->val > y->val;
        };
        priority_queue<ListNode* , vector<ListNode*> , decltype(comp)> pq(comp);
        for(auto l : lists) 
            if(l) pq.push(l);
            
        while(pq.size())
        {
            ListNode* top = pq.top();
            pq.pop();
            tail->next = top;
            tail = tail->next;
            top = top->next;
            if(top) pq.push(top);
        }
        ListNode* ret = phead->next;
        delete phead;
        return ret;
    }
};